package datastructure;

/**
 * 斐波那契数
 * <p>
 * 从数列的第三项开始，每一项都等于前两项之和
 * 0 1 1 2 3 5 8 13
 * </p>
 *
 * @author miweidong
 * @date 2021-10-14 9:45
 */
public class Fibonacci {
    public static void main(String[] args) {
        int fun1 = fibonacciFun1(6);
        System.out.println("for循环形式：" + fun1);
        int fun2 = fibonacciFun2(6);
        System.out.println("递归形式：" + fun2);
    }

    /**
     * 循环方式求第n个斐波那契数
     * 时间复杂度针对于代码中最多次执行的代码块，即下列for循环
     * O(n) = n
     *
     * @param n 第n个位置
     * @return n位置的斐波那契数
     */
    public static int fibonacciFun1(int n) {
        if (n <= 1) {
            return n;
        }
        int first = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }

    /**
     * 斐波那契数递归方法
     * O(n) = 2的（n-1）次  - 1
     * 时间复杂度：O(n) ~ 2的n次方
     *
     * @param n 第n个位置
     * @return n位置的斐波那契数
     */
    public static int fibonacciFun2(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacciFun1(n - 1) + fibonacciFun1(n - 2);
    }

}
